package Algorithm.DynamicPlanning;
// 牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w。
// 牛牛家里一共有n袋零食, 第i袋零食体积为v[i]。 牛牛想知道在总体积不超过背包容量的情况下，
// 他一共有多少种零食放法(总体积为0也算一种放法)。
public class Code01_SnacksWays {

    public static int ways1(int[] arr, int w){
        return process(arr, 0, w);
    }

    public static int process(int[] arr, int index, int rest){
        if (rest < 0){
            return -1;
        }
        if (index == arr.length){
            return 1;
        }
        int next1 = process(arr, index + 1, rest); // 不要
        int next2 = process(arr, index + 1, rest - arr[index]); // 要
        return next1 + (next2 == -1 ? 0 : next2);
    }
    // ways2根据ways1推理而来，没什么道理,暴力递归改动态规划
    public static int ways2(int[] arr, int w){
        int N = arr.length;
        int[][] dp = new int[N + 1][w + 1];
        for (int j = 0; j <= w; j++){
            dp[N][j] = 1;
        }
        for (int i = N - 1; i >= 0 ; i--) { // i对应index,j对应w
            for (int j = 0; j <= w; j++){
                dp[i][j] = dp[i + 1][j] + (j - arr[i] >= 0 ? dp[i + 1][j - arr[i]] : 0);
            }
        }
        return dp[0][w];
    }

    // dp[i][j]表示index :0-i的零食体积严格组合成体积j
    public static int ways3(int[] arr, int w){
        int N = arr.length;
        int[][] dp = new int[N][w + 1];
        // 赋值边界
        for (int i = 0; i < N; i++) {
            dp[i][0] = 1; // 0-i组合出体积为0的方法数为1（不要）
        }
        if (arr[0] <= w){
            dp[0][arr[0]] = 1;
        }
        // 普遍情况
        for (int i = 1; i < N; i++) {
            for (int j = 1; j <= w; j++){
                // 0~i-1已经凑出j；0~i-1已经凑出j - arr[i]，加上自己arr[i]刚好
                dp[i][j] = dp[i - 1][j] + (j - arr[i] >= 0 ? dp[i - 1][j - arr[i]] : 0);
            }
        }
        int res = 0;
        // 把最后一行结果加起来
        for (int j = 0; j <= w; j++) {
            res += dp[N - 1][j];
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {4, 3, 2, 9};
        int w = 8;
        System.out.println(ways1(arr, w));
        System.out.println(ways2(arr, w));
        System.out.println(ways3(arr, w));
    }
}
